package com.lxq.dataStructure.sort;

public class quickSort {
    public static int partition(int[] A, int low, int high) {
        if (low > high) {
            return -1;
        }
        //pivot就是基准位
        int pivot = A[low];

        while (low < high) {
            //先看右边，依次往左递减
            while (A[high] >= pivot && low < high) {
                high--;
            }
            A[low] = A[high];
            //再看左边，依次往右递增
            while (A[low] <= pivot && low < high) {
                low++;
            }
            A[high] = A[low];
        }
        //最后将基准为与i和j相等位置的数字交换
        A[low] = pivot;
        return low;
    }

    public static void qSort(int[] A, int low, int high) {
        if (low < high) {
            int pivotpos = partition(A, low, high);
            //递归调用左半数组
            qSort(A, low, pivotpos - 1);
            //递归调用右半数组
            qSort(A, pivotpos + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        qSort(arr, 0, arr.length - 1);
        for (int j : arr) {
            System.out.println(j);
        }
    }
}